#if !defined(PARALOGY_TREE_H)
#define  PARALOGY_TREE_H

// standard headers
#include <vector>
#include <string>
#include <iostream>
#include <utility>
#include <cassert>
#include <stdexcept>
#include <deque>
#include <map>

// boost headers
#include <boost/tuple/tuple.hpp>

// my headers
#include "ultoa.h"

// forward declaration
namespace bcpp_matrix
{
template <typename T> struct t_matrix;
typedef t_matrix<float> t_matrix_f;
}
namespace bcpp_tree
{

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_node

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
class t_invalid_tree : public std::logic_error
{
public:
	explicit t_invalid_tree(const std::string&  arg) : std::logic_error(arg){}
};

// pre-declarations
class t_tree;
class do_sort_by_name;
//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_node

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
class t_node
{
	friend class t_tree;
	friend class do_sort_by_name;
	t_tree*							tree;
	std::vector<t_node*>			children;
	float							length;
	t_node* 						parent;
									// UID is unique for this node belong to each tree
									// is actually offset into tree's array of nodes
	unsigned						UID;
									// only leaves have leaf_UID
									// is actually offset into tree's data for leaves
									// e.g. names etc.
	int								leaf_UID;
	void				set_parent(t_node& new_parent);
						// assumes two children
	void				change_child(const t_node* old_child, t_node* new_child);
	t_node*				get_sibling_of(const t_node* node) const;
public:
	void				swap(t_node& other);
	void				print(std::ostream& os) const;

	t_tree*				get_tree() const			{	return tree;					}
	t_node*				get_child(unsigned i)		{	return children[i];				}
	const t_node*		get_child(unsigned i) const	{	return children[i];				}
	unsigned			get_children_count() const	{	return children.size();			}
	unsigned			get_UID()	const			{	return UID; 					}
	float				get_length() const			{	return length;					}
	int					get_leaf_UID() const		{	return leaf_UID;				}
	const std::string&	get_name() const;
	const std::string&	get_label() const;
	t_node*				get_parent()				{	return parent;					}
	const t_node*		get_parent() const			{	return parent;					}
	bool				is_leaf() const				{	return leaf_UID >= 0;			}

	void				set_length(float l)			{length = l;					}
	void				set_name(const std::string& n);
	void				set_label(const std::string& l);
private:
						t_node(t_tree* tree_, unsigned UID_, int leaf_UID_,
								const std::string& name);
};

inline void t_node::swap(t_node& other)
{
	std::swap(tree, other.tree);
	std::swap(children, other.children);
	std::swap(length,  other.length);
	std::swap(leaf_UID,  other.leaf_UID);
	std::swap(UID     ,  other.UID     );
	std::swap(parent  ,  other.parent  );
}

inline void swap(t_node& a, t_node& b)
{
	a.swap(b);
}

inline t_node* t_node::get_sibling_of(const t_node* node) const
{
	assert(children.size() == 2);
	if (children[0] == node)
		return children[1];
	else
		return children[0];
}
inline void t_node::change_child(const t_node* old_child, t_node* new_child)
{
	assert(children.size() == 2);
	if (children[0] == old_child)
		children[0] = new_child;
	else
		children[1] = new_child;
}

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_edge

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct t_edge
{
	bcpp_tree::t_node* parent;
	bcpp_tree::t_node* child;
	t_edge(bcpp_tree::t_node* parent_, bcpp_tree::t_node* child_):
		parent(parent_), child(child_) {}
};

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_tree

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
class t_tree
{
public:
	friend class 				t_node;
		friend t_node* node_from_old_UID(unsigned oldUID, t_tree& new_tree, const std::vector<unsigned>& old_UIDs_to_new);
	typedef						t_node 	t_node_type;
private:
	std::string					name;
	t_node_type*		 		root;
	t_node_type* 				current_node;
	t_node_type* 				current_parent;
	bool 						finished;
	std::deque<t_node_type>		shared_mem;
	std::vector<std::string>	node_names;
	std::vector<std::string>	node_labels;
	std::vector<t_node_type*>	leaves;
	t_node_type& 				add_node(bool is_leaf, const std::string& str, int leaf_UID = -1);
	bool						sort_by_names_alphabetically;
	void						assert_consistency(t_node*) const;
	void						recursively_copy_tree(const t_node& node, t_node& new_node, t_tree& new_tree,
											const std::vector<unsigned>& old_UIDs_to_new) const;
public:
	void			set_name(const std::string& n) {name = n;}
	std::string		get_name() const { return name;}
	void			assert_consistency() const;
	bool			reroot(unsigned child, unsigned grandchild,
						   float& child_length, float& grandchild_length, 
						   float& other_length);
	bool			undo_reroot(unsigned child_index, unsigned grandchild_index,
								float child_length, float grandchild_length, 
								float other_length);
	void			reroot(t_node* new_parent, t_node* new_child);

	bool			get_sort_by_names() const {return sort_by_names_alphabetically;}
	void			set_sort_by_names(bool s) {sort_by_names_alphabetically = s;}
	const std::vector<std::string>&	get_node_names () const	{return node_names;}
	std::vector<std::string>		get_leaf_names () const;
	const std::vector<std::string>&	get_node_labels () const{return node_labels;}

	void			to_matrix(bcpp_matrix::t_matrix_f& matrix) const;
	std::string		to_nh_str() const;
	void			reset();
	unsigned		get_leaf_count() const	{	return leaves.size();		}
	unsigned		get_node_count() const	{	return shared_mem.size();	}
	t_node_type*	get_root() const {	return root;	}
	t_node_type&	get_leaf(unsigned i) {	assert(i < get_leaf_count()); return *leaves[i];	}
	const t_node_type&	get_leaf(unsigned i)  const {	assert(i < get_leaf_count()); return *leaves[i];	}
	const t_node_type&	get_node(unsigned UID) const {	assert(UID < get_node_count()); return shared_mem[UID];	}
	t_node_type&	get_node(unsigned UID) {	assert(UID < get_node_count()); return shared_mem[UID];	}
					// find which child matches a supplied
	unsigned		find_child(t_node* parent, t_node* child) const;

	t_tree();
	t_node_type&	add_leaf(const std::string& str, int leaf_UID = -1);
	t_node_type&	add_internal_node();
	t_node_type&	join_nodes(t_node_type& node1, t_node_type& node2);
	void 			label_current_node(const std::string& str);
	bool 			reparent_to_grandparent();
	void 			set_branch_len(const std::string& str);
	void 			set_branch_len(float len);
	bool 			finish();
	bool			is_finished() const {return finished;}
	void			get_normalized_tree(t_tree& new_tree) const;
	template <typename T> void for_each(T& t);
	template <typename T> void for_each(T& t) const;
};

//________________________________________________________________________________________

//	for_each

//________________________________________________________________________________________
template <typename T> void t_tree::for_each(T& t)
{
	t(root);
//	for (unsigned i = 0; i < root->children.size(); ++i)
//		t(root->children[i]);
}

template <typename T> void t_tree::for_each(T& t) const
{
	t(root);
//	for (unsigned i = 0; i < root->children.size(); ++i)
//		t(root->children[i]);
}



//________________________________________________________________________________________

//	new_hampshire format

//________________________________________________________________________________________
boost::tuple<bool, std::string>
		load_tree_from_newhampshire_format_str(const std::string& tree_str, t_tree& tree);



//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	t_node inlines

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
inline const std::string& t_node::get_name() const
{
	return tree->node_names[UID];
}
inline const std::string& t_node::get_label() const
{
	return tree->node_labels[UID];
}
inline void t_node::set_name(const std::string& n)
{
	tree->node_names[UID] =n;
}
inline void t_node::set_label(const std::string& l)
{
	tree->node_labels[UID] = l;
}





class t_tree_parsing_from_stream_error : public std::logic_error
{
public:
	explicit t_tree_parsing_from_stream_error(	const std::string& tree_name,
												const std::string& error,
												unsigned			line_num) :
		std::logic_error(	"Invalid tree "  +
							(tree_name.length() ? ("for " + tree_name) :tree_name)
							+ " on line "
							+ ultoa(line_num) +
							": [" + error + "]."){}
};





//________________________________________________________________________________________

//	read_tree_from_stream

//________________________________________________________________________________________
// N.B. Will not allow more than one tree on a line
bool read_tree_from_stream(std::istream& istrm, bcpp_tree::t_tree& tree,
							unsigned& cnt_lines);
bool read_treestr_from_stream(	std::istream& istrm,
								std::string& tree_str,
								std::string& tree_name,
								unsigned& cnt_lines);

struct t_tree_io_wrapper
{
	bcpp_tree::t_tree&	tree;
	unsigned&				line_num;
	t_tree_io_wrapper(bcpp_tree::t_tree& tree_, unsigned& line_num_)
					:tree(tree_), line_num(line_num_){}
};

inline std::istream& operator >>(std::istream& istrm, t_tree_io_wrapper tree)
{
	if (!read_tree_from_stream(istrm, tree.tree, tree.line_num))
		istrm.setstate(std::ios::failbit);
	return istrm;
}


std::ostream& operator <<(std::ostream& ostrm, const bcpp_tree::t_tree& tree);
std::ostream& operator <<(std::ostream& ostrm, const bcpp_tree::t_node& node);

/*
class t_tree_not_in_stream_error : public std::logic_error
{
public:
	explicit t_tree_not_in_stream_error() :
		std::logic_error("No tree in New Hampshire format was found."){}
};


 */















}
#endif


